/**
 * @(#) IterAnalysis��2008-7-22
 * Copyright 2008 Program Analysis Research Group(PARG),Institute of Software, Peking University.
 * All rights reserved.
 */
package graphclustering;

import graphclustering.data.Cluster;
import graphclustering.util.ClusteringUtils;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Random;

import org.apache.commons.cli.CommandLine;
import org.apache.commons.cli.CommandLineParser;
import org.apache.commons.cli.Options;
import org.apache.commons.cli.ParseException;
import org.apache.commons.cli.PosixParser;

/**
 * @author HeLi
 */
public class IterAnalysis {
    static class Node {
        Object self;

        Cluster parent;

        boolean isNON;

        public Node(Cluster parent, Object self) {
            this.parent = parent;
            this.self = self;
            if (isLeaf()) {
                isNON = false;
            }
        }

        public void setNON(boolean isNON) {
            this.isNON = isNON;
        }

        public boolean isNON() {
            return this.isNON;
        }

        public boolean isLeaf() {
            return self instanceof String;
        }

        public boolean canPrune(Node node) {
            if (this.isLeaf()) {
                if (node.isLeaf()) {
                    return this.parent == node.parent;
                } else {
                    return false;
                }
            } else {
                if (node.isLeaf()) {
                    return false;
                } else {
                    return this.parent == node.parent
                            && ((Cluster) self).clusterChildren.size() == 0
                            && ((Cluster) node.self).clusterChildren.size() == 0
                            && ((Cluster) self).atomicNodeIDList.size() == 0
                            && ((Cluster) node.self).atomicNodeIDList.size() == 0;
                }
            }
        }

        public boolean isSinglePrunable() {
            if (isLeaf()) {
                return true;
            } else {
                Cluster c = (Cluster) self;
                if (c.atomicNodeIDList.size() != 0
                        || c.clusterChildren.size() != 0)
                    return false;
                if (c.parent != null) {
                    if (c.parent.clusterChildren.size() > 1) {
                        return false;
                    } else {
                        if (c.parent.clusterChildren.get(0) == c) {
                            return true;
                        } else {
                            return false;
                        }
                    }
                } else {
                    return true;
                }
            }
        }

        public void prune() {
            if (this.parent == null) {
                return;
            }

            if (isLeaf()) {
                this.parent.atomicNodeIDList.remove(self);
                // System.out.println("prune leaf=" + self);
            } else {
                Cluster c = (Cluster) self;
                if (c.atomicNodeIDList.size() > 0
                        || c.clusterChildren.size() > 0) {
                    System.out
                            .println("Prune wrong node,with[atomicNodeIDList size="
                                    + c.atomicNodeIDList.size()
                                    + ",clusterChildren size="
                                    + c.clusterChildren.size() + "]");
                }
                this.parent.clusterChildren.remove(self);
                // System.out.println("prune cluster=" + ((Cluster)
                // self).label);
            }
        }
    }

    protected static List<Collection<Node>> scan4Prunables(
            List<Node> workingQueue) {
        List<Collection<Node>> result = new ArrayList<Collection<Node>>();

        for (int i = 0; i < workingQueue.size(); i++) {
            List<Node> prunable = new ArrayList<Node>();
            Node current = workingQueue.get(i);
            for (int j = i + 1; j < workingQueue.size(); j++) {
                Node prior = workingQueue.get(j);
                if (current.canPrune(prior)) {
                    prunable.add(prior);
                    i++;
                } else {
                    break;
                }
            }
            if (prunable.size() > 0) {
                prunable.add(current);
            } else {
                if (current.isSinglePrunable()) {
                    prunable.add(current);
                }
            }
            if (prunable.size() > 0 && checkPrunable(prunable, current)) {
                result.add(prunable);
            }
        }
        return result;
    }

    private static boolean checkPrunable(List<Node> prunable, Node sample) {
        if (sample.parent != null) {
            if (sample.isLeaf()) {
                return prunable.size() == sample.parent.atomicNodeIDList.size();
            } else {
                return prunable.size() == sample.parent.clusterChildren.size();
            }
        } else {
            return true;
        }
    }

    protected static int countNoneLeafNode(List<Node> workingQueue) {
        int c = 0;
        for (Node node: workingQueue) {
            if (node.isNON) {
                c++;
            }
        }
        return c;
    }

    protected static List<Float> analysis(Cluster rawroot, int rounds) {
        List<Float> result = new ArrayList<Float>();
        for (int k = 0; k < rounds; k++) {
            List<Integer> orbit = new ArrayList<Integer>();
            Cluster root = rawroot.clone();
            ClusteringUtils.label(root);
            List<Node> workingQueue = new ArrayList<Node>();
            List<Node> dfsQueue = new ArrayList<Node>();
            dfsQueue.add(new Node(null, root));
            while (!dfsQueue.isEmpty()) {
                Node head = dfsQueue.remove(0);
                workingQueue.add(head);
                if (!head.isLeaf()) {
                    Cluster self = (Cluster) head.self;
                    for (Cluster child: self.clusterChildren) {
                        dfsQueue.add(new Node(self, child));
                    }
                    for (String child: self.atomicNodeIDList) {
                        dfsQueue.add(new Node(self, child));
                    }
                }
            }
            Random random = new Random();
            while (workingQueue.size() > 0) {
                List<Collection<Node>> prunables = scan4Prunables(workingQueue);
                if (prunables.size() > 0) {
                    int selection = random.nextInt(prunables.size());
                    Collection<Node> prunable = prunables.get(selection);
                    markNON(workingQueue, prunable);
                    for (Node node: prunable) {
                        node.prune();
                        workingQueue.remove(node);
                    }
                    orbit.add(countNoneLeafNode(workingQueue));
                } else {
                    System.out.println("dead lock, no prunables found!");
                }

            }

            if (result.size() == 0) {
                for (Integer o: orbit)
                    result.add((float) o);
            } else {
                if (result.size() != orbit.size()) {
                    System.out
                            .println("analysis meets different iter count for iter: "
                                    + k
                                    + "![expected="
                                    + result.size()
                                    + ",orbit=" + orbit.size() + "]");
                    System.exit(1);
                }
                for (int i = 0; i < orbit.size(); i++) {
                    float origin = result.get(i);
                    result.set(i, origin + orbit.get(i));
                }
            }
            System.out.println("records for iter:" + k);
            for (int o: orbit) {
                System.out.println(o);
            }
            System.out.println("----------------");
        }

        for (int i = 0; i < result.size(); i++) {
            float origin = result.get(i);
            result.set(i, origin / rounds);
        }
        return result;
    }

    /**
     * @param workingQueue
     * @param prunable
     */
    private static void markNON(List<Node> workingQueue,
            Collection<Node> prunable) {
        Node sample = prunable.iterator().next();
        if (sample.parent != null) {
            Node sampleParent = null;
            for (Node node: workingQueue) {
                if (node.self == sample.parent) {
                    sampleParent = node;
                    break;
                }
            }
            if (sampleParent != null) {
                sampleParent.isNON = true;
            } else {
                System.out.println("Parent for prunable not found!");
            }
        }
    }

    public static void main(String[] args) {
        CommandLineParser parser = new PosixParser();
        Options options = new Options();
        options.addOption("i", "input-file", true,
                "input clustering result file");
        options.addOption("r", "rounds", true, "how many rounds should i run?");
        String inputFile = null;
        int rounds = 7;
        try {
            // parse the command line arguments
            CommandLine line = parser.parse(options, args);

            // validate that block-size has been set
            if (!line.hasOption("i")) {
                // print the value of block-size
                System.out.println("No input clustering result given!");
                System.exit(1);
            }

            inputFile = line.getOptionValue("i");

            if (line.hasOption("r")) {
                rounds = Integer.parseInt(line.getOptionValue("r"));
            }
        } catch (ParseException exp) {
            System.out.println("Unexpected exception:" + exp.getMessage());
        }

        if (inputFile == null) {
            System.exit(0);
        }

        Cluster cluster = null;
        try {
            BufferedReader reader = new BufferedReader(new FileReader(new File(
                    inputFile)));
            String line = reader.readLine();
            reader.close();

            cluster = ClusteringUtils.parse(line);
        } catch (IOException ioe) {
            System.out.println("Unexpected IOException:" + ioe.getMessage());
        } catch (Exception exp) {
            System.out
                    .println("Unexpected parse exception:" + exp.getMessage());
        }

        if (cluster == null) {
            System.exit(0);
        }

        try {
            List<Float> result = analysis(cluster, rounds);
            for (int i = 0; i < result.size(); i++) {
                System.out.println(result.get(i));
            }
        } catch (Exception exp) {
            System.out.println("Unexpected analysis exception:"
                    + exp.getMessage());
            exp.printStackTrace();
        }

    }
}
